//sortedType.cpp
/********************************************************************************
*																				*
*	Author:			Jared Szechy												*
*	Assignment:		Assignment 3												*
*	Class:			CPS-151														*
*	Instructor:		V. Starkley													*
*	Due Date:		September 20												*
*																				*
*	This file implements the SortedType class.									*
*																				*
********************************************************************************/

#include "sortedType.h"

void SortedType::MakeEmpty()
{
    length = 0;
}

SortedType::SortedType()
{
    length = 0;
}

bool SortedType::IsFull() const
{
    return (length == MAX_ITEMS);
}

int SortedType::LengthIs() const
{
    return length;
}

bool SortedType::RetrieveItem(ItemType& item)
{
	int low = 0;
	int high = length;
	int mid;

	while (low <= high)
	{
		mid = (low + high) / 2;

		if (info[mid] == item)
		{
			item = info[mid];
			return true;
		}
		else if (info[mid] < item)
			low = mid + 1;
		else
			high = mid - 1;
   }

	return false;
}

bool SortedType::InsertItem(ItemType item)
{
	//if list is not full, item is stored in next available space.
	if (length == MAX_ITEMS)
		return false;
	else
	{
		int i = length;
		while (i > 0 && info[i -1] > item)
		{
			info[i] = info[i - 1];
			i--;
		}
		info[i] = item;
		length++;
		return true;
	}
}

bool SortedType::DeleteItem(ItemType item)
{
    int low = 0;
	int high = length;
	int mid;
	int location;
	bool found = false;

	//find the item
	while (low <= high)
	{
		mid = (low + high) / 2;

		if (info[mid] == item)
		{
			location = mid;
			length--;
			found = true;
			break;
		}
		else if (info[mid] < item)
			low = mid + 1;
		else
			high = mid - 1;
	}
	for (int i = location; i < length; i++)
		info[i] = info[i + 1];
	return found;
}


void SortedType::ResetList()
{
    currentPos = 0;
}

bool SortedType::GetNextItem(ItemType& item)
{
    if (currentPos == length)
	{
		return false;
	}
	else
	{
		item = info[currentPos];
		currentPos++;
		return true;
	}
}


